<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>power</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>power</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>

<h3>Prototype</h3>
<tt>Power</tt> is an overloaded name; there are actually two <tt>power</tt>
functions.
<pre>
template &lt;class T, class Integer&gt;
inline T power(T x, Integer n);

template &lt;class T, class Integer, class <A href="MonoidOperation.html">MonoidOperation</A>&gt;
T power(T x, Integer n, MonoidOperation op);
</pre>		   
<h3>Description</h3>
<tt>Power</tt> is generalized exponentiation: it raises the value <tt>x</tt>
to the power <tt>n</tt>, where <tt>n</tt> is a non-negative integer.  
<P>
The first version of <tt>power</tt>
returns <tt>x</tt> raised to the <tt>n</tt>th power; that is, it returns
<tt>x * x ... * x</tt>, where <tt>x</tt> is repeated <tt>n</tt> times. <A href="#1">[1]</A>  If
<tt>n == 0</tt>, then it returns <tt><A href="MonoidOperation.html">identity_element</A>(<A href="times.html">multiplies</A>&lt;T&gt;())</tt>.
<P>
The second version of <tt>power</tt> is just like the first except
that it uses an arbitrary <A href="MonoidOperation.html">Monoid Operation</A> instead of 
<tt><A href="times.html">multiplies</A>&lt;T&gt;</tt>, returning <tt><A href="MonoidOperation.html">identity_element</A>(op)</tt>
when <tt>n == 0</tt>.
<P>
<b>Important note</b>: <tt>power</tt> does not assume that multiplication is
commutative, but it does rely crucially on the fact that
multiplication is associative.  If you have defined <tt>*</tt> or
<tt><A href="MonoidOperation.html">MonoidOperation</A></tt> to be a non-associative operation, then <tt>power</tt>
<i>will give you the wrong answer</i>.  <A href="#2">[2]</A>
<h3>Definition</h3>
Defined in the standard header <A href="numeric">numeric</A>, and in the nonstandard
backward-compatibility header <A href="algo.h">algo.h</A>.  This function is an SGI
extension; it is not part of the C++ standard.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt><A href="times.html">multiplies</A>&lt;T&gt;</tt> is a model of <A href="MonoidOperation.html">Monoid Operation</A>.
<LI>
<tt>Integer</tt> is an integral type.
</UL>
For the second version:
<UL>
<LI>
<tt>MonoidOperation</tt> is a model of <A href="MonoidOperation.html">Monoid Operation</A>.
<LI>
<tt>T</tt> is <tt>MonoidOperation</tt>'s argument type.
<LI>
<tt>n</tt> is an integral type.
</UL>
<h3>Preconditions</h3>
<UL>
<LI>
<tt>n &gt;= 0</tt>.
</UL>
<h3>Complexity</h3>
The number of multiplications (or, in the case of the second version,
the number of applications of <tt>MonoidOperation</tt>) is <tt>lg(n) + nu(n)</tt>
where <tt>lg</tt> is the base 2 logarithm and <tt>nu(n)</tt> is the number of 
<tt>1</tt>s in the binary representation of <tt>n</tt>. <A href="#3">[3]</A>
<h3>Example</h3>
<pre>
int main() {
  cout &lt;&lt; &quot;2 ** 30 = &quot; &lt;&lt; power(2, 30) &lt;&lt; endl;
}
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
This is a conceptual description of what <tt>power</tt>'s return value 
is; it is not how <tt>power</tt> is actually implemented.  If <tt>power</tt>
were implemented that way then it would require <tt>n-1</tt> multiplications,
which would be grossly inefficient.  <tt>Power</tt> is implemented using
the &quot;Russian peasant algorithm&quot;, which requires only <tt>O(log n)</tt>
multiplications.
See section 4.6.3 of Knuth (D. E. Knuth, <i>The Art of Computer
Programming.  Volume 2: Seminumerical Algorithms</i>, 
Addison-Wesley, 1981) for a discussion.
<P><A name="2">[2]</A>
See the <A href="MonoidOperation.html">Monoid Operation</A> requirements for a discussion of associativity.
<P><A name="3">[3]</A>
This is in fact not the minimum possible number of multiplications:
it is possible to compute the fifteenth power of <tt>x</tt> using only
five multiplications, but <tt>power(x, 15)</tt> uses six.  
<h3>See also</h3>
<A href="MonoidOperation.html">Monoid Operation</A>, 
<tt><A href="times.html">multiplies</A></tt>, 
<tt><A href="plus.html">plus</A></tt>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
